/*
*
给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。

示例 1：

输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。
示例 2：

输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106

  - @author ala
  - @date 2024-09-18 17:27
*/
package main

import (
	"fmt"
	"math"
)

func main() {
	grid := [][]int{{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}}
	//grid := [][]int{
	//	{3, 2, 4},
	//	{2, 1, 9},
	//	{1, 1, 7}}

	fmt.Println(maxMoves(grid))
}

func maxMoves(grid [][]int) int {
	return V1(grid)
}

var INF int = math.MaxInt >> 1

/**
 *	1）原地修改
 *	2）从左往右遍历每一列
 *		如果 min(grid[i - 1][j - 1], grid[i][j - 1], grid[i + 1][j - 1]) < grid[i][j]，则 grid[i][j] 不变
 *		否则 grid[i][j] = INF
 *	3）若某一列全是INF，则该列无法遍历，返回前一列
 */
func V1(grid [][]int) int {
	M, N := len(grid), len(grid[0])

	for j := 1; j < N; j++ {
		check := false
		for i := 0; i < M; i++ {
			if grid[i][j] == INF {
				continue
			}

			lt := INF
			if i > 0 {
				lt = grid[i-1][j-1]
			}
			ll := grid[i][j-1]
			lb := INF
			if i < M-1 {
				lb = grid[i+1][j-1]
			}

			if min(lt, ll, lb) >= grid[i][j] {
				grid[i][j] = INF
			} else {
				check = true
			}
		}
		if !check {
			return j - 1
		}
	}

	return N - 1
}
